#pragma once

/// 顺序表类型定义

template <typename T, int M>
struct SqList
{
    T elem[M];
    int length;
};

/// 顺序表初始化 InitList(&L)
template <typename T, int M>
void InitList(SqList<T, M> &L)
{
    L.length = 0;
}

/// 顺序表插入 ListInsert(&L, i, e)
template <typename T, int M>
void ListInsert(SqList<T, M> &L, int i, T e)
{
    // 若表满，则抛出异常
    if (L.length == M)
        throw "L is full";
    // 若 i 不合法，则抛出异常
    if (i < 1 || i > L.length + 1)
        throw "Invalid i";

    // 移动元素 [i-1..n-1] -> [i..n]
    for (int j = L.length - 1; j >= i - 1; j--)
        L.elem[j + 1] = L.elem[j];

    // 插入元素 e
    L.elem[i - 1] = e;

    // 表长加 1
    L.length++;
}

/// 顺序表删除 ListDelet(&L, i, &e)
template <typename T, int M>
void ListDelete(SqList<T, M> &L, int i, T &e)
{
    // 若表空，或 i 不合法，抛出异常
    if (L.length == 0)
        throw "L is empty";
    if (i < 1 || i > L.length)
        throw "Invalid i";

    // 取出元素
    e = L.elem[i - 1];

    // 移动元素

    for (int j = i; j < L.length; j++)
        L.elem[j - 1] = L.elem[j];

    // 表长减 1
    L.length--;
}
